package codingforgreat.class39;


// 来自百度
// 给定一个字符串str，和一个正数k
// str子序列的字符种数必须是k种，返回有多少子序列满足这个条件
// 已知str中都是小写字母
// 原始是取mod
// 本节在尝试上，最难的
// 搞出桶来，组合公式
public class Class03_SequenceKDifferentKinds {
    public static int nums(String s, int k) {
        char[] str = s.toCharArray();
        int N = str.length;
        int[] cnt = new int[26];
        for (char c : str) {
            cnt[c - 'a']++;
        }
        return ways(cnt,0,k);
    }
    public static int math(int n) {
        return (1 << n) - 1;
    }
    private static int ways(int[] c, int i, int r) {
        if (r == 0) {
            return 1;
        }
        if (i == c.length) {
            return 0;
        }
        // math(n) -> 2 ^ n -1
        return math(c[i]) * ways(c, i + 1, r - 1) + ways(c, i + 1, r);
    }
    public static void main(String[] args) {
        String str = "acbbca";
        int k = 3;
        System.out.println(nums(str, k));
    }

}
